Lexical Specification & DFAs

1. Lexing Procedure
2. Finite Automata

This part focuses on how to partition the input string into tokens.

1. Lexing Procedure

we first write down the regex for each token class
construct a gigantic regex \(R\) to match all lexemes for all tokens
suppose the input is \(x_1 \dots x_n\), for a prefix \(x_1 \dots x_i\), check if this prefix satisfies the regex \(R\).
if yes, then we remove the prefix as a token. and then, find which token class this prefix belongs to.

Q1. How much input is used? What if \(x_1\dots x_i \in L(R)\) and also \(x_1\dots x_j\in L(R)\) where \(i\ne j\) ? It turns out that we should pick the longest possible string in \(L(R)\).

Q2. What if a token satisfies multiple token classes? i.e. \(\text{prefix}(i)\in L(R_j)\) and \(\text{prefix}(i)\in L(R_k)\). In this case, we should give priority to token classes, and pick the token class with highest priority, e.g., for token if, keywords token class should be prioritized before variables.

Q3. What if no rule matches? We should write an “error handling” case with lowest priority to match all “bad strings”.

2. Finite Automata

Regular expressions = specification, while finite automata = implementation. A finite automata consists of input alphabet \(\Sigma\), a set of state \(S\), a start state \(n\), a set of accepting states \(F\subseteq S\) and a set of transitions \(\text{state} \overset{\text{input}}{\longrightarrow} \text{state}\).

\(\epsilon\)-move: Machine can move from state A to state B without reading input. This only exists in NFA.
Deterministic Finite Automata (DFA): Exactly one transition per input per state. No \(\epsilon\)-moves.
Non-deterministic Finite Automata (NFA): Can have zero, one or multiple transitions for one input in a given state. Can have \(\epsilon\)-moves. NFA accepts if the input can get to an accepting state.

DFAs are faster to execute, while NFAs are generally (exponentially) smaller.

2.1. Converting Regex into NFAs

Practically, we use NFAs to implement regular expressions. Then we translate NFAs into DFAs, and finally use look-up tables to implement DFAs.

Our task is to define an NFA for each kind of regex.

For \(\epsilon\)-move, we can define

\[ \boxed{\text{state}} \overset{\epsilon}{\longrightarrow} \boxed{\text{accept}} \]

For single character, we can define

For union,

For concat,

For iteration,

2.2. From NFAs to DFAs

\(\epsilon\)-closure: A \(\epsilon\)-closure of a state \(S\), is the set of nodes that can be reached by only using \(\epsilon\)-moves zero or more times

If a NFA have \(N\) states, then in its equivalent DFA, there’re at most \(2^N-1\) non-empty subsets.

“Construction of DFA”. We first introduce some notations, suppose in NFA

state set \(S\)
start state \(s\)
accepting state \(F\)
suppose \(a\) is a character in the input language. we define \(a(X)\) to be the set of states \(y\) such that there exists some state \(x\) in \(X\) that has a transition from \(x\) to \(y\) through \(a\). i.e.

\[ a(X)=\set{y:x\in X \land x \overset{a}{\to} y} \]

\(\epsilon\)-closure operator \(C(X)\).

For the equivalent DFA to the above NFA, we have

Property	NFA	DFA
states	\(S\)	subsets of \(S\)
start state	\(s\)	\(C(s)\)
final states	\(F\)	\( \set{X:X\cap F\ne \emptyset} \)
transition		\( X\overset{a}{\to}Y \) if \( C(a(X))=Y \)

2.3. Implementation of Finite Automata

A DFA can be implemented by a 2D table T, with one dimension being states and the other dimension being input symbols. For every transition \( s_i \overset{a}{\to} s_j \), we set \( \texttt{T}[s_i, a]=s_j \).

Sometimes, we may directly implement NFA for memory concerns. We can also use 2D table with an extra column for \( \epsilon \)-moves and each cell should be a set of states.